插入排序法(Insertion Sort)是排序演算法的一種
他是一種簡單容易理解的排序演算法
其概念是利用另一個數列來存放已排序部分
逐一取出未排序數列中元素
從已排序數列由後往前找到適當的位置插入
建立一個新的陣列
一個一個元素去和陣列中比較
插入在正確的地方
然而實作上通常不使用額外的數列來儲存已排序的部分
而使用原地In-place的方式來完成
數列的左半部表示已排序部分
右半部表示未排序部分
不另外使用數列
在與已排序的部分比較時
利用指派(Assign)的方式將元素往右位移
來達到插入的效果
因為位移的關係需要有另一個變數來暫存最右邊的數值
最佳時間複雜度：O(n)
平均時間複雜度：O(n^2)
最差時間複雜度：O(n^2)
空間複雜度：O(1)
Stable sort：是
iThome鐵人賽
看影片追技術